{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Merge Of Two Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestMerge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造字典序最大的合并字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>word1</code> 和 <code>word2</code> 。你需要按下述方式构造一个新字符串 <code>merge</code> ：如果 <code>word1</code> 或 <code>word2</code> 非空，选择 <strong>下面选项之一</strong> 继续操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>word1</code> 非空，将 <code>word1</code> 中的第一个字符附加到 <code>merge</code> 的末尾，并将其从 <code>word1</code> 中移除。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，<code>word1 = \"abc\" </code>且 <code>merge = \"dv\"</code> ，在执行此选项操作之后，<code>word1 = \"bc\"</code> ，同时 <code>merge = \"dva\"</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>如果 <code>word2</code> 非空，将 <code>word2</code> 中的第一个字符附加到 <code>merge</code> 的末尾，并将其从 <code>word2</code> 中移除。\n",
    "\t<ul>\n",
    "\t\t<li>例如，<code>word2 = \"abc\" </code>且 <code>merge = \"\"</code> ，在执行此选项操作之后，<code>word2 = \"bc\"</code> ，同时 <code>merge = \"a\"</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你可以构造的字典序 <strong>最大</strong> 的合并字符串<em> </em><code>merge</code><em> 。</em></p>\n",
    "\n",
    "<p>长度相同的两个字符串 <code>a</code> 和 <code>b</code> 比较字典序大小，如果在 <code>a</code> 和 <code>b</code> 出现不同的第一个位置，<code>a</code> 中字符在字母表中的出现顺序位于 <code>b</code> 中相应字符之后，就认为字符串 <code>a</code> 按字典序比字符串 <code>b</code> 更大。例如，<code>\"abcd\"</code> 按字典序比 <code>\"abcc\"</code> 更大，因为两个字符串出现不同的第一个位置是第四个字符，而 <code>d</code> 在字母表中的出现顺序位于 <code>c</code> 之后。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word1 = \"cabaa\", word2 = \"bcaaa\"\n",
    "<strong>输出：</strong>\"cbcabaaaaa\"\n",
    "<strong>解释：</strong>构造字典序最大的合并字符串，可行的一种方法如下所示：\n",
    "- 从 word1 中取第一个字符：merge = \"c\"，word1 = \"abaa\"，word2 = \"bcaaa\"\n",
    "- 从 word2 中取第一个字符：merge = \"cb\"，word1 = \"abaa\"，word2 = \"caaa\"\n",
    "- 从 word2 中取第一个字符：merge = \"cbc\"，word1 = \"abaa\"，word2 = \"aaa\"\n",
    "- 从 word1 中取第一个字符：merge = \"cbca\"，word1 = \"baa\"，word2 = \"aaa\"\n",
    "- 从 word1 中取第一个字符：merge = \"cbcab\"，word1 = \"aa\"，word2 = \"aaa\"\n",
    "- 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word1 = \"abcabc\", word2 = \"abdcaba\"\n",
    "<strong>输出：</strong>\"abdcabcabcaba\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= word1.length, word2.length <= 3000</code></li>\n",
    "\t<li><code>word1</code> 和 <code>word2</code> 仅由小写英文组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-merge-of-two-strings](https://leetcode.cn/problems/largest-merge-of-two-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-merge-of-two-strings](https://leetcode.cn/problems/largest-merge-of-two-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cabaa\"\\n\"bcaaa\"', '\"abcabc\"\\n\"abdcaba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        q1 = deque(word1)\n",
    "        q2 = deque(word2)\n",
    "        ans = []\n",
    "\n",
    "        while q1 or q2:\n",
    "            if q1 > q2:\n",
    "                ans.append(q1.popleft())\n",
    "            else:\n",
    "                ans.append(q2.popleft())\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        q1, q2, ans = deque(word1), deque(word2), []\n",
    "        while q1 or q2:\n",
    "            if q1 > q2:\n",
    "                ans.append(q1.popleft())\n",
    "            else:\n",
    "                ans.append(q2.popleft())\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        ans = []\n",
    "        l1,l2 = map(deque,[word1,word2])\n",
    "        while l1 or l2:\n",
    "            if l1 > l2: ans.append(l1.popleft())\n",
    "            else: ans.append(l2.popleft())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = \"\"\n",
    "        while word1 and word2:\n",
    "            if word1 > word2:\n",
    "                merge += word1[0]\n",
    "                word1 = word1[1:]\n",
    "            else:\n",
    "                merge += word2[0]\n",
    "                word2 = word2[1:]\n",
    "            \n",
    "        return merge + word1 + word2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        i = j = 0\n",
    "        ans = []\n",
    "        while i < len(word1) and j < len(word2):\n",
    "            if word1[i:] > word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        ans.append(word1[i:])\n",
    "        ans.append(word2[j:])\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        q1, q2, ans = deque(word1), deque(word2), []\n",
    "        while q1 or q2:\n",
    "            if q1 > q2:\n",
    "                ans.append(q1.popleft())\n",
    "            else:\n",
    "                ans.append(q2.popleft())\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        a, b = deque(word1), deque(word2)\n",
    "        res = \"\"\n",
    "        while a or b:\n",
    "            res += max(a, b).popleft()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        ans = ''\n",
    "        i, j = 0, 0\n",
    "        while i < len(word1) or j < len(word2):\n",
    "            if i == len(word1):\n",
    "                ans += word2[j:]\n",
    "                break\n",
    "            if j == len(word2):\n",
    "                ans += word1[i:]\n",
    "                break\n",
    "\n",
    "            if word1[i:] >= word2[j:]:\n",
    "                ans += word1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += word2[j]\n",
    "                j += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = []\n",
    "        i, j, n, m = 0, 0, len(word1), len(word2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and word1[i:] > word2[j:]:\n",
    "                merge.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merge.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(merge)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        \n",
    "        # 贪心算\n",
    "        wordlist1=word1\n",
    "        wordlist2=word2\n",
    "\n",
    "        walker1=0\n",
    "        walker2=0\n",
    "        result=\"\"\n",
    "\n",
    "        # 不是合并数组？\n",
    "        # 每次选择字典序较大的后缀\n",
    "        while(walker1!=len(wordlist1) or walker2!=len(wordlist2)):\n",
    "            # 贪心算法思想，后文中字典序较大的放前面；\n",
    "            if walker1<len(wordlist1) and wordlist1[walker1:]>=wordlist2[walker2:]:\n",
    "                result+=wordlist1[walker1]\n",
    "                walker1+=1\n",
    "            else:\n",
    "                result+=wordlist2[walker2]\n",
    "                walker2+=1\n",
    "        return result\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        q1, q2, ans = deque(word1), deque(word2), []\n",
    "        while q1 and q2:\n",
    "            if q1 > q2:\n",
    "                ans.append(q1.popleft())\n",
    "            else:\n",
    "                ans.append(q2.popleft())\n",
    "        if q1:\n",
    "            ans.extend(list(q1))\n",
    "        else:\n",
    "            ans.extend(list(q2))\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = []\n",
    "        i, j, n, m = 0, 0, len(word1), len(word2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and word1[i:] > word2[j:]:\n",
    "                merge.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merge.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(merge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        # 贪心，每次取字典序大的\n",
    "        i = j = 0\n",
    "        m,n = len(word1),len(word2)\n",
    "        ans = []\n",
    "        while i < m or j < n:\n",
    "            if i < m and word1[i:] > word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        i,j=0,0\n",
    "        m=''\n",
    "        while i<len(word1) or j<len(word2):\n",
    "            if i==len(word1): m,j=m+word2[j:],len(word2)\n",
    "            elif j==len(word2): m,i=m+word1[i:],len(word1)\n",
    "            else:\n",
    "                if word1[i]>word2[j]:\n",
    "                    m+=word1[i]\n",
    "                    i+=1\n",
    "                elif word1[i]<word2[j]:\n",
    "                    m+=word2[j]\n",
    "                    j+=1\n",
    "                elif word1[i:] > word2[j:]:\n",
    "                    m+=word1[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    m+=word2[j]\n",
    "                    j+=1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        \"\"\"\n",
    "            每次从两个字符串里面选择一个字典序更大的字符串\n",
    "        \n",
    "        \"\"\"\n",
    "        m, n = len(word1), len(word2)\n",
    "        ans = []\n",
    "        p = 0 # word2的下标\n",
    "\n",
    "        # case1:\n",
    "        # for i, x in enumerate(word1):\n",
    "            \n",
    "        #     while p < n and ord(word2[p]) > ord(x):\n",
    "        #         ans.append(word2[p])\n",
    "        #         p += 1\n",
    "            \n",
    "        #     ans.append(x)\n",
    "        # ans.append(word2[p:])\n",
    "\n",
    "        # # case2:\n",
    "        # ans2 = []\n",
    "        # p = 0\n",
    "        # for i, x in enumerate(word2):\n",
    "            \n",
    "        #     while p < n and ord(word1[p]) > ord(x):\n",
    "        #         ans2.append(word1[p])\n",
    "        #         p += 1\n",
    "            \n",
    "        #     ans2.append(x)\n",
    "        # ans2.append(word1[p:])\n",
    "        # if ''.join(ans) > ''.join(ans2):\n",
    "        #     return ''.join(ans)\n",
    "        # else:\n",
    "        #     return ''.join(ans2)\n",
    "        ans = []\n",
    "        i, j = 0, 0\n",
    "        while i < len(word1) or j < len(word2):\n",
    "            if word1[i:] >= word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        i = j = 0\n",
    "        ans = []\n",
    "        while i < len(word1) and j < len(word2):\n",
    "            if word1[i:] > word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        ans.append(word1[i:])\n",
    "        ans.append(word2[j:])\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        l1 = len(word1)\n",
    "        l2 = len(word2)\n",
    "        i = j = 0\n",
    "        ret = ''\n",
    "        while i < l1 and j < l2:\n",
    "            if word1[i] == word2[j]:\n",
    "                if word1[i:] >= word2[j:]:\n",
    "                    ret += word1[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ret += word2[j]\n",
    "                    j += 1 \n",
    "            elif word1[i] > word2[j]:\n",
    "                ret += word1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                ret += word2[j]\n",
    "                j += 1\n",
    "        if i < l1:\n",
    "            ret += word1[i:]\n",
    "        else:\n",
    "            ret += word2[j:]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "         n1=len(word1)\n",
    "         n2=len(word2)\n",
    "         ans=\"\"\n",
    "         while word1 and word2:\n",
    "            if word1>=word2:\n",
    "\n",
    "               cur=word1[0]\n",
    "               word1=word1[1:]\n",
    "               ans+=cur\n",
    "            else:\n",
    "               cur=word2[0]\n",
    "               word2=word2[1:]\n",
    "               ans+=cur\n",
    "\n",
    "         if word1:\n",
    "            ans+=word1\n",
    "         else:\n",
    "            ans+=word2\n",
    "         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = []\n",
    "        i, j, n, m = 0, 0, len(word1), len(word2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and word1[i:] > word2[j:]:\n",
    "                merge.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merge.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(merge)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        a, b = deque(word1), deque(word2)\n",
    "        res = \"\"\n",
    "        while a or b:\n",
    "            res += max(a, b).popleft()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        \"\"\"\n",
    "            每次从两个字符串里面选择一个字典序更大的字符串\n",
    "        \n",
    "        \"\"\"\n",
    "        m, n = len(word1), len(word2)\n",
    "        ans = []\n",
    "        p = 0 # word2的下标\n",
    "\n",
    "        # case1:\n",
    "        # for i, x in enumerate(word1):\n",
    "            \n",
    "        #     while p < n and ord(word2[p]) > ord(x):\n",
    "        #         ans.append(word2[p])\n",
    "        #         p += 1\n",
    "            \n",
    "        #     ans.append(x)\n",
    "        # ans.append(word2[p:])\n",
    "\n",
    "        # # case2:\n",
    "        # ans2 = []\n",
    "        # p = 0\n",
    "        # for i, x in enumerate(word2):\n",
    "            \n",
    "        #     while p < n and ord(word1[p]) > ord(x):\n",
    "        #         ans2.append(word1[p])\n",
    "        #         p += 1\n",
    "            \n",
    "        #     ans2.append(x)\n",
    "        # ans2.append(word1[p:])\n",
    "        # if ''.join(ans) > ''.join(ans2):\n",
    "        #     return ''.join(ans)\n",
    "        # else:\n",
    "        #     return ''.join(ans2)\n",
    "        ans = []\n",
    "        i, j = 0, 0\n",
    "        while i < len(word1) or j < len(word2):\n",
    "            if word1[i:] >= word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = []\n",
    "        i, j, n, m = 0, 0, len(word1), len(word2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and word1[i:] > word2[j:]:\n",
    "                merge.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merge.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(merge)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        res = []\n",
    "\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(word1) or j < len(word2):\n",
    "            if i < len(word1) and j < len(word2):\n",
    "                if word1[i] > word2[j]:\n",
    "                    res.append(word1[i])\n",
    "                    i += 1\n",
    "                elif word2[j] > word1[i]:\n",
    "                    res.append(word2[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    if word1[i:] >= word2[j:]:\n",
    "                        res.append(word1[i])\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        res.append(word2[j])\n",
    "                        j += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        res = ''.join(res)\n",
    "        if i == len(word1):\n",
    "            return res + word2[j:]\n",
    "        else:\n",
    "            return res + word1[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge=''\n",
    "        while word1 and word2:\n",
    "            if word1>word2:\n",
    "                merge+=word1[0]\n",
    "                word1=word1[1:]\n",
    "            else:\n",
    "                merge+=word2[0]\n",
    "                word2=word2[1:]\n",
    "        return merge+word1+word2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        ans = ''\n",
    "        i, j = 0, 0\n",
    "        while i < len(word1) or j < len(word2):\n",
    "            if i == len(word1):\n",
    "                ans += word2[j]\n",
    "                j += 1\n",
    "            elif j == len(word2):\n",
    "                ans += word1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                a, b = word1[i], word2[j]\n",
    "                if a > b:\n",
    "                    ans += a\n",
    "                    i += 1\n",
    "                elif a < b:\n",
    "                    ans += b\n",
    "                    j += 1\n",
    "                else:\n",
    "                    if word1[i:] >= word2[j:]:\n",
    "                        ans += a\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        ans += b\n",
    "                        j += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = ''\n",
    "        while word1 and word2:\n",
    "            if word1>word2:\n",
    "                merge += word1[0]\n",
    "                word1 = word1[1:]\n",
    "            else :\n",
    "                merge += word2[0]\n",
    "                word2 = word2[1:]\n",
    "        return merge+word1+word2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        ans = []\n",
    "        i,j = 0,0\n",
    "        m,n = len(word1),len(word2)\n",
    "        while i < m or j < n:\n",
    "            if i < m and word1[i:] > word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = ''\n",
    "        while word1 and word2:\n",
    "            if word1>word2:\n",
    "                merge += word1[0]\n",
    "                word1 = word1[1:]\n",
    "            else :\n",
    "                merge += word2[0]\n",
    "                word2 = word2[1:]\n",
    "        return merge+word1+word2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "\n",
    "        lis_word1 = list(word1)\n",
    "        lis_word2 = list(word2)\n",
    "        tmp = []\n",
    "        while lis_word1 and lis_word2:\n",
    "            if lis_word1 > lis_word2:\n",
    "                tmp.append(lis_word1.pop(0))\n",
    "            else:\n",
    "                tmp.append(lis_word2.pop(0))\n",
    "        \n",
    "        if lis_word1:\n",
    "            tmp += lis_word1\n",
    "        if lis_word2:\n",
    "            tmp += lis_word2\n",
    "        \n",
    "        return ''.join(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        merge = []\n",
    "        i, j, n, m = 0, 0, len(word1), len(word2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and word1[i:] > word2[j:]:\n",
    "                merge.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merge.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(merge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\r\n",
    "        # @cache \r\n",
    "        # def dfs(i: int, j: int) -> str:\r\n",
    "        #     if i == len(word1) and j == len(word2):\r\n",
    "        #         return \"\"\r\n",
    "        #     if i == len(word1):\r\n",
    "        #         return word2[j:]\r\n",
    "        #     if j == len(word2):\r\n",
    "        #         return word1[i:]\r\n",
    "        #     if word1[i] > word2[j]:\r\n",
    "        #         return word1[i] + dfs(i + 1, j)\r\n",
    "        #     elif word1[i] < word2[j]:\r\n",
    "        #         return word2[j] + dfs(i, j + 1)\r\n",
    "        #     return word1[i] + max(dfs(i, j + 1), dfs(i + 1, j))\r\n",
    "        # return dfs(0, 0)\r\n",
    "    \r\n",
    "        # 暴力判断后边是可行的 \r\n",
    "\r\n",
    "        res = []\r\n",
    "        i, j = 0, 0 \r\n",
    "        while i < len(word1) and j < len(word2):\r\n",
    "            if word1[i:] > word2[j:]:\r\n",
    "                res.append(word1[i])\r\n",
    "                i += 1\r\n",
    "            else :\r\n",
    "                res.append(word2[j])\r\n",
    "                j += 1\r\n",
    "        res = \"\".join(res)\r\n",
    "        if i != len(word1):\r\n",
    "            res += word1[i:]\r\n",
    "        else:\r\n",
    "            res += word2[j:]\r\n",
    "        return res \r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        res = []\n",
    "        i, j = 0, 0\n",
    "        if word1 < word2:\n",
    "            word1, word2 = word2, word1\n",
    "        word1, word2 = list(word1), list(word2)\n",
    "        while i<len(word1) and j<len(word2):\n",
    "            # if word1[i] < word2[j]:\n",
    "            #     res.append(word2[j])\n",
    "            #     j+=1\n",
    "            # elif word1[i] > word2[j]:\n",
    "            #     res.append(word1[i])\n",
    "            #     i+=1\n",
    "            # else:\n",
    "                if word1[i:] >= word2[j:]:\n",
    "                    res.append(word1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(word2[j])\n",
    "                    j += 1\n",
    "\n",
    "        while i<len(word1):\n",
    "            res.append(word1[i])\n",
    "            i+=1\n",
    "        while j<len(word2):\n",
    "            res.append(word2[j])\n",
    "            j+=1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        i = j = 0\n",
    "        ans = []\n",
    "        while i < len(word1) and j < len(word2):\n",
    "            if word1[i:] > word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        ans.append(word1[i:])\n",
    "        ans.append(word2[j:])\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        # 贪心 谁字典序大就选谁\n",
    "        merge = []\n",
    "        i,j,n,m = 0,0,len(word1),len(word2)\n",
    "        while i < n or j < m:\n",
    "            if i < n and word1[i:] > word2[j:]:\n",
    "                merge.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merge.append(word2[j])\n",
    "                j += 1\n",
    "        return ''.join(merge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        result = ''\n",
    "        l = 0\n",
    "        r = 0\n",
    "        while l != len(word1) and r != len(word2):\n",
    "            if word1[l] > word2[r]:\n",
    "                result += word1[l]\n",
    "                l += 1\n",
    "            elif word2[r] > word1[l]:\n",
    "                result += word2[r]\n",
    "                r += 1\n",
    "            else:\n",
    "                if self.compare(word1, word2, l, r):\n",
    "                    result += word1[l]\n",
    "                    l += 1\n",
    "                else:\n",
    "                    result += word2[r]\n",
    "                    r += 1\n",
    "        if l == len(word1):\n",
    "            result += word2[r:]\n",
    "        if r == len(word2):\n",
    "            result += word1[l:]\n",
    "        return result\n",
    "    \n",
    "    def compare(self, word1, word2, l, r):\n",
    "        while l != len(word1) and r != len(word2):\n",
    "            if word1[l] == word2[r]:\n",
    "                l += 1\n",
    "                r += 1\n",
    "                continue\n",
    "            if word1[l] > word2[r]:\n",
    "                l += 1\n",
    "                r += 1\n",
    "                return True\n",
    "            else:\n",
    "                l += 1\n",
    "                r += 1\n",
    "                return False\n",
    "        if l == len(word1):\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        n1 = len(word1)\n",
    "        n2 = len(word2)\n",
    "        p1 = p2 = 0\n",
    "        res = []\n",
    "        while p1 < n1 and p2 < n2:\n",
    "            if word1[p1:] + word2[p2:] > word2[p2:] + word1[p1:]:\n",
    "                res.append(word1[p1])\n",
    "                p1 += 1\n",
    "            else:\n",
    "                res.append(word2[p2])\n",
    "                p2 += 1\n",
    "        \n",
    "        if p1 == n1:\n",
    "            return ''.join(res) + word2[p2:]\n",
    "        else:\n",
    "            return ''.join(res) + word1[p1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        m, n = len(word1), len(word2)\n",
    "        ans = \"\"\n",
    "        while word1 and word2:\n",
    "            if word1 > word2:\n",
    "                ans += word1[0]\n",
    "                word1 = word1[1:]\n",
    "            else:\n",
    "                ans += word2[0]\n",
    "                word2 = word2[1:]\n",
    "        return ans+word1+word2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, s1: str, s2: str) -> str:\n",
    "        ans = ''\n",
    "        while s1 and s2:\n",
    "            if s1 > s2:\n",
    "                ans += s1[0]\n",
    "                s1 = s1[1:]\n",
    "            else:\n",
    "                ans += s2[0]\n",
    "                s2 = s2[1:]\n",
    "        ans += s1 + s2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        i = j = 0\n",
    "        ans = []\n",
    "        while i < len(word1) and j < len(word2):\n",
    "            if word1[i:] > word2[j:]:\n",
    "                ans.append(word1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(word2[j])\n",
    "                j += 1\n",
    "        ans.append(word1[i:])\n",
    "        ans.append(word2[j:])\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        s = \"\"\n",
    "        i = j = 0\n",
    "        n, m = len(word1), len(word2)\n",
    "        while i < n and j < m:\n",
    "            if word1[i:] > word2[j:]:\n",
    "                s += word1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                s += word2[j]\n",
    "                j += 1\n",
    "        if i < n:\n",
    "            s += word1[i:]\n",
    "        if j < m:\n",
    "            s += word2[j:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMerge(self, word1: str, word2: str) -> str:\n",
    "        res = []\n",
    "        i, j = 0, 0\n",
    "        if word1 < word2:\n",
    "            word1, word2 = word2, word1\n",
    "        word1, word2 = list(word1), list(word2)\n",
    "        while i<len(word1) and j<len(word2):\n",
    "            if word1[i] < word2[j]:\n",
    "                res.append(word2[j])\n",
    "                j+=1\n",
    "            elif word1[i] > word2[j]:\n",
    "                res.append(word1[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                if word1[i:] >= word2[j:]:\n",
    "                    res.append(word1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(word2[j])\n",
    "                    j += 1\n",
    "\n",
    "        while i<len(word1):\n",
    "            res.append(word1[i])\n",
    "            i+=1\n",
    "        while j<len(word2):\n",
    "            res.append(word2[j])\n",
    "            j+=1\n",
    "        return \"\".join(res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
